\chapter{面向网络协同应用编程的数据平面配置生成研究}
\label{cha:dpg}
本章的研究重点在于解决数据平面配置生成问题，旨在实现可验证路由编程的路由生成过程，为网络协同应用编程生成满足应用需求的数据平面配置。首先，本章分析了网络协同应用编程中存在的“路由冲突”现象，引出了生成满足应用需求的数据平面配置的问题，通过分析直观思路，提出路径标签冲突的挑战。为了应对这一挑战，提出了数据平面配置生成系统Fusion。Fusion将数据平面配置生成问题建模为SAT（可满足性问题）和整数规划问题，实现了基于定长编码和前缀编码的数据平面配置生成方法。最后，通过实验验证，相比已有工作，Fusion将路由规则匹配域长度缩减了75\%。

\cref{fig:dpg-outline}列出了数据平面配置生成的主要问题、挑战和方案。首先在\cref{sec:dpg-background}中阐述了面向网络协同应用编程的数据平面配置生成研究背景，在\cref{sec:dpg-problem}中，对数据平面配置生成问题进行描述并提出直观思路，在\cref{sec:dpg-challenge}中提出解决问题所面临的挑战，在\cref{sec:dpg-solution-fixed}和\cref{sec:dpg-solution-var}中针对挑战提出基于定长和前缀的数据平面配置生成方法，并在\cref{sec:dpg-eval}中对所提出的解决方案进行实验验证。

\begin{figure}[h]
  \centering
  \includegraphics[width=1\linewidth]{figures/dpg/outline.pdf}
  \caption{面向网络协同应用编程的数据平面配置生成研究路径}
  \label{fig:dpg-outline}
\end{figure}

\section{面向网络协同应用编程的数据平面配置生成研究背景}
\label{sec:dpg-background}
在第 \ref{cha:socker} 章中，Socker框架主要描述了单个应用的网络与应用协同编程，基于Socker的应用程序生成相应的数据平面需求，对于一个数据平面需求，很容易生成其对应的数据平面配置。然而，在实际网络中往往存在大量的应用，各应用具有不同的数据平面需求，需要生成相应的数据平面配置满足所有的数据平面需求。然而，数据平面的资源是有限的，如何准确配置数据平面，并实现优化的数据平面配置是实现网络与应用协同编程的关键问题之一。

\textbf{网络协同应用编程中的“路由冲突”现象。}在进行网络协同应用编程时，应用通常会发送具有不同路径需求的数据包。虽然使用Socker框架等工具可以在终端主机上对这些数据包进行区分和标记，但一旦这些数据包进入网络数据平面，它们的上下文信息就会丢失。这意味着，网络设备无法有效地识别和区分这些数据包，尤其是当它们具有相同的目的地址时，这会导致路由冲突和混淆。

例如，在\cref{fig:dpg-background-conflict}中的网络拓扑中，终端主机H1上的应用发送了三种种具有不同路径需求的数据包，其中路径1和2目的为H3，路径3目的为H2。如果简单的通过目的IP进行路由（如\cref{fig:dpg-background-conflict}中表格所示为E1的路由表），会发现路径3能够被正确处理，但路径1和2的数据包都具有相同的目的地址，当它们到达设备E1时，由于缺乏上下文信息，E1无法准确判断这些数据包应该沿哪条路径继续传输，从而引发了路由冲突。本文将上述现象称为网络协同应用编程中的“路由冲突”现象。


\begin{figure}[ht]
  \centering
  \includegraphics[width=\linewidth]{figures/dpg/background-conflict.pdf}
  \caption{网络协同应用编程中的“路径冲突”现象示例}
  \label{fig:dpg-background-conflict}
\end{figure}

导致“路由冲突”现象的根本原因在于数据包没有携带足够的路由需求信息。通过分析\cref{fig:dpg-background-conflict}中应用发出的两种数据包的包头，可以发现它们之间唯一的不同之处是传输层的源端口号。然而，在Socker编程框架下，源端口号是由操作系统自动分配的临时端口，因此不能作为唯一区分数据包的可靠特征。如果网络设备依赖源端口号来区分数据包并作出路由决策，大量的临时端口号分配和销毁，导致触发大量的路由更新操作。为解决这一问题，需要在数据包中引入更多的路由需求信息元数据，使数据包能够明确传达应用的路由偏好。这些元数据将允许网络设备更精确地选择适当的路径来满足应用的需求，从而避免路由冲突的发生。

% 例如，因为会丢失入口信息，基于入口的路由不能在路径中间的交换机中正确处理数据包。并且当数据包在路径的一个交换机上被转换时，必须正确调整转换后安装在后续交换机上的规则。
% \textbf{网络协同应用编程中的路径爆炸（Path explosion）现象。}
% 在实际网络中，不同的应用对数据平面有不同的需求，对于一个终端设备互通的网络$G(D,L)$，如果平均每个终端设备有$N$个应用，平均每个应用产生$Q$个数据流类型，则最多产生$O((|term(D)| \times N)^2 \times Q)$个路径需求。而对于一个网络设备$d \in D$，如果有$N$个数据平面需求的路径通过$d$，则$d$的FIB需要$N$条规则。本文将上述现象称为“路径爆炸”（Path explosion）现象。在\cref{fig:dpg-example-topo}所示的示例拓扑中，部署于终端设备A、B、C和D的应用通过Socker系统互相通信，总共生成12个数据平面需求，以网络设备S3为例探讨其需要生成的FIB规则。\cref{tab:dpg-reqs}列出了所有路径经过S3的数据平面需求，总共包含10个数据平面需求，用$h_{i,j}$表示应用$i$向应用$j$发出的数据包头。如果对每个数据平面需求都生成一条的规则，则S3上需要生成10条规则。当网络规模和应用数量较大时，需要生成大量的数据平面规则。传统的基于IP地址聚合方法并不适用于网络协同应用场景，因为Socker除了利用五元组作为数据平面需求的路径标识，对目的IP聚合后其他包头域（如源端口号）会发生冲突。


% 在这样的背景下，一种生成数据平面配置的直接方式是采用类似MPLS（Multi-Protocol Label Switching）或者SR（Source Routing）的方式对所有路径分配一个唯一路径标签，这样的方式需要大于$O(|term(D)| \times N)$~\footnote{此处忽略了一次方变量$Q$}个比特位，在大规模网络情况下可能会超过协议能表达的最大包头长度（如MPLS标签长度只有20位），且该方案对标签的利用率较低，比如两个完全不重叠的路径可以共用同一个标签。所以，需要一种更加紧凑的路径标签生成方法，能够利用最短的标签长度使数据平面能够正确表示所有应用的需求。同时，由于Socker框架在终端通过eBPF处理数据包，Socker可以对数据包做任意的操作，如NAT（Network Address Translation），使得Socker可以很容易集成上述路径编码功能，从而实现更高效紧凑的数据平面配置生成。

% \begin{figure}[]
%   \centering
%   \includegraphics[width=0.8\linewidth]{figures/dpg/example-topo.pdf}
%   \caption{数据平面配置生成示例拓扑}
%   \label{fig:dpg-example-topo}
% \end{figure}

% \begin{table}[]
%   \center
%   \caption{路径经过S3的数据平面需求及FIB规则}
%   \label{tab:dpg-reqs}
%   \begin{tabular}{|c|c|c|c|c|c|}
%     \hline
%     $\rho$ & $d$ & $h$ & $\pi$ & match & nexthop
%     \\\hline
%     $\rho_{A,B}$ & A & $h_{A,B}$ & S1-S3-S2-B & $h_{A,B}$ & S2
%     \\\hline
%     $\rho_{A,C}$ & A & $h_{A,B}$ & S1-S3-S4-S5-C & $h_{A,C}$ & S4
%     \\\hline
%     $\rho_{A,D}$ & A & $h_{A,B}$ & S1-S3-S4-S6-D & $h_{A,D}$ & S4
%     \\\hline
%     $\rho_{B,A}$ & B & $h_{B,A}$ & S2-S3-S1-A & $h_{B,A}$ & S1
%     \\\hline
%     $\rho_{B,C}$ & B & $h_{B,C}$ & S2-S3-S4-S5-C & $h_{B,C}$ & S4
%     \\\hline
%     $\rho_{B,D}$ & B & $h_{B,A}$ & S2-S3-S4-S6-D & $h_{B,D}$ & S4
%     \\\hline
%     $\rho_{C,A}$ & C & $h_{C,A}$ & S5-S4-S3-S1-A & $h_{C,A}$ & S1
%     \\\hline
%     $\rho_{C,B}$ & C & $h_{C,B}$ & S5-S4-S3-S2-B & $h_{C,B}$ & S2
%     \\\hline
%     $\rho_{D,A}$ & D & $h_{D,A}$ & S6-S4-S3-S1-A & $h_{D,A}$ & S1
%     \\\hline
%     $\rho_{D,B}$ & D & $h_{D,B}$ & S6-S4-S3-S2-B & $h_{D,B}$ & S2
%     \\\hline
%   \end{tabular}
% \end{table}




\section{面向网络协同应用编程的数据平面配置生成问题描述}
\label{sec:dpg-problem}
\textbf{P1: 如何生成满足所有应用需求的数据平面配置。}Socker应用提供了数据平面需要实现的路径集合，对数据平面来说，需要生成满足所有应用需求的数据平面配置。具体而言，网络需要生成相应的数据平面配置$\mathcal{R} = \{R_1,...,R_{|net(D)|}\}$以满足应用需求，首先，$\mathcal{R}$必须是正确的。

\begin{definition}
  \label{def:dpg-correctness}
	\textbf{数据平面配置的正确性}。给定一个路径集合$\Pi = \{\pi_1,...,\pi_N\}$，令$\mathcal{R}$为数据平面配置，对于任意一个路径$\pi_i \in \Pi$，令$src_i$为$\pi_i$的起始设备，如果$\exists h: \mathcal{F}(src_i, h, \mathcal{R}) = \pi_i$，则数据平面配置$\mathcal{R}$对于路径集合$\Pi$是正确的，表示为$\mathcal{R} \succ \Pi$。
\end{definition}

此外，生成的数据平面配置还应最大程度地减少对设备资源的占用，特别是TCAM内存。因此，必须确保生成的路由规则数量尽可能少，并且这些规则的匹配域长度应尽量缩短。这种做法不仅能够有效减小设备内存的占用，还有助于减少数据包的包头长度，从而最小化数据包头引入的传输开销，所以，数据平面配置生成的一种直观思路是采用标签路由，具体描述如下。

\textbf{I1: 对所有路径分配唯一标签。} 生成正确的数据平面配置相对容易，一种通用方法是使用标签路由\cite{sourcerouting,pathswitching}技术。给定一个路径集合$\Pi$，可以使用长度为$\lceil log_2 |\Pi| \rceil$的标签作为匹配域生成数据平面规则，数据包在进入网络之前向数据包头附加该标签，在出口处去掉该标签即可。如\cref{fig:dpg-intuition-tag}所示的例子，采用了路径标签方法来解决\cref{fig:dpg-background-conflict}中提出的需求问题。对于三条路径，可以使用两位长度的标签编码，例如，路径1的编码为00，路径2的编码为01，路径3的编码为10。然后，设备E1的数据平面配置可以生成如\cref{fig:dpg-intuition-tag}中所示的表格。

在数据传输过程中，由于Socker框架在终端主机通过eBPF处理数据包，Socker可以对数据包执行各种自定义操作，例如NAT（Network Address Translation）或标签增加（Push Tag）等。这使得Socker可以轻松地集成路径标签功能，从而实现更高效和更紧凑的数据平面配置生成。例如，当数据通过\cref{fig:dpg-intuition-tag}中的路径1发送时，H1的Socker程序可以在内核态对绑定路径1的数据包增加一个2位的标签00。然后，在数据包到达H3时，H3的eBPF程序可以去除该标签以还原数据包。另一种兼容的方式是直接使用传输层的源端口号作为标签承载域，从而避免了H3上的标签操作。这种方式提供了更高的效率和灵活性，以满足不同应用需求。

\begin{figure}[ht]
  \centering
  \includegraphics[width=\linewidth]{figures/dpg/intuition-tag.pdf}
  \caption{标签冲突示例}
  \label{fig:dpg-intuition-tag}
\end{figure}

网络内部的交换机只需要匹配该标签并转发到相应端口。然而，简单地为每条路径分配唯一的标签可能会导致每个交换机上的规则数量爆炸，例如，具有$k$个终端设备的端到端网络路径数量可以多达$O(k^2)$个，也就意味着网络设备可能需要$O(k^2)$个规则来匹配这些标签。

% 对于一个数据平面需求$\rho(d, h, \pi)$，如果$\pi \subseteq \mathbb{T}(d, h)$，
% % 如果$\forall \rho(d, h, \pi) \in \mathbb{R}: \pi \subseteq \mathbb{T}(d, h)$，
% 则本文称数据平面配置$\mathbb{T}$对数据平面需求$\rho$是有效的，表示为$\mathbb{T} \sim \rho$。相应的，如果$\forall \rho(d, h, \pi) \in \mathbb{R}: \mathbb{T} \sim \rho$，则数据平面配置$\mathbb{T}$对数据平面需求集合$\mathbb{R}$是有效的，表示为$\mathbb{T} \sim \mathbb{R}$。

% \todo{}
% \begin{theorem}
% 	对于数据平面需求$\rho_i \subseteq \rho_j$，如果$\mathbb{T} \sim \rho_j$，则$\mathbb{T} \sim \rho_i$。
% \end{theorem}



% \begin{definition}
% 	\label{def:dpg-optimal}
% 	\textbf{数据平面配置最优性}。对于数据平面配置$\mathbb{T} \succ \Pi$，如果$\nexists \mathbb{T}' \succ \Pi$，且：
%   \begin{enumerate}
%     \item 规则数量较少：$\sum_{T \in \mathbb{T}'}|T| < \sum_{T \in \mathbb{T}}|T|$；
%     \item 最长的match域长度较小：$\max_{r \in \cup_{T \in \mathbb{T}'}T} |r.match| < \max_{r \in \cup_{T \in \mathbb{T}}T} |r.match|$
%   \end{enumerate}
%   则数据平面配置$\mathbb{T}$是最优的。
% \end{definition}

% 数据平面配置的最优性主要体现在两个方面：1）数据平面配置具有最少的规则数量，从而节省更多的设备内存；2）数据平面配置规则最长的match域最小使得数据包头的长度最小，从而最小化数据包头引入的传输开销。

% 为了生成最优的数据平面配置，理想情况下，一个交换机的规则数应该等于路径上的输出端口数，已有工作如Path switching\cite{opo} 通过为每个链路引入可前缀度标签来减少每个交换机上的规则数量，但是没有考虑在交换机之间重复使用标签（例如，两个完全不同的路径可以共用一个标签），这导致了标签长度压缩率的损失，并引入了额外的开销来存储标签指针。


% 本文的方法使用固定长度编码来禁止转换开销，并使用SAT求解器推导出具有最小长度的端口和路径编码。

% \textbf{P1: 如何生成正确且最优的数据平面配置。}基于\cref{def:dpg-correctness}和\cref{def:dpg-optimal}，本文定义数据平面配置生成问题如下：对于一个网络$G(D,L)$和一个数据平面需求的路径集合$\Pi$，生成网络的数据平面配置$\mathbb{T}$，使得$\mathbb{T} \succ \Pi$且$\mathbb{T}$是最优的。


% \section{面向网络协同应用编程的数据平面配置生成基本思路}
% \label{sec:dpg-intuition}


\section{面向网络协同应用编程的数据平面配置生成的挑战}
\label{sec:dpg-challenge}
尽管I1方法（为所有路径分配唯一标签）在小规模网络中简单而高效，但对于大规模网络，不同应用对数据平面的需求不尽相同。考虑一个允许终端设备互通的网络$G(D,L)$，如果平均每个终端设备有$N$个应用，每个应用平均产生$Q$个不同的路径需求类型，那么最多可能会产生$O((|term(D)| \times N)^2 \times Q)$种不同的路径需求。这就需要的标签长度为$\lceil \log_2((|term(D)| \times N)^2 \times Q) \rceil = \lceil 2 \times (\log_2 |term(D)| + \log_2 N) + \log_2 Q \rceil$。以一个拥有128个终端设备（$|term(D)|=128$）为例，平均每个终端设备有16个应用（$N=16$），每个应用平均产生4种路径需求（$Q=4$），需要的标签长度将达到24位。即便是在当前支持MPLS协议的网络中，MPLS标签长度的最大限制为20位，也无法应对这种大规模网络的路径标签分配需求。此外，对于网络中的每个设备，其上的每条路径都需要在设备上生成一条路由规则，这将严重占用核心设备的资源。具体而言，本文将面向网络协同应用编程的数据平面配置生成的挑战描述如下：

\textbf{C1: 路径标签空间浪费。}对所有路径进行唯一标签编码将会产生极大地路径标签空间浪费，首先，对于任意两条互不相交的路径（Disjoint paths），它们可以共用同一个路径标签。例如，\cref{fig:dpg-challenge-disjoint}中所示的例子中有3条路径，若按照I1的方法至少需要2个比特位作为标签，然而，由于其中2个路径（蓝色和绿色）互不相交，所以它们可以共用同一个标签，最终用1位即可实现所需功能。

\begin{figure}[htp]
  \centering
  \includegraphics[width=.5\linewidth]{figures/dpg/challenge-disjoint.pdf}
  \caption{路径互不相交可以重用标签}
  \label{fig:dpg-challenge-disjoint}
\end{figure}


此外，对于没有互不相交的路径情况，也可以通过合适的标签规划实现更短的标签编码长度。如图 \ref{fig:ope-example} 所示为一个包含4个交换机和3个主机的网络，需要编码6条端到端路径（列在图 \ref{fig:ope-example} 的表格中），其它们都在设备E1处相交。如果按照I1的方法编码，至少需要3个比特位来编码6条路径，但是在本例中，2个比特位即可完成编码。图 \ref{fig:ope-example} 中表格的第二列展示了一种可能的路径编码方式，以及在拓扑图中标记了分配给每个端口的标签。

\begin{figure}[ht]
  \centering
  \includegraphics[width=0.8\linewidth]{figures/dpg/challenge-encode.pdf}
  \caption{通过合理的标签规划缩短标签长度}
  \label{fig:ope-example}
\end{figure}

所以，路径标签的编码方式直接对标签的长度产生影响，且编码方法受到路径之间的相互关系影响，在网络协同应用编程环境下，需要探索一种更加紧凑的路径标签编码方法，从而应对大规模网络中海量的应用需求，已有工作如Path switching~\cite{opo}提供了一种变长的基于多个标签的编码方式，该方式在\cref{fig:ope-example}的例子中需要跟长的比特位编码，（6个比特位，其中4个比特位用于路径编码，2个比特位用于标签指针）。另外，在Path switching中，指针必须在路径的每一跳进行更新，从而导致每个交换机需要复杂的解析器和频繁的指针转换，这尤其会损害软件交换机的性能。为了实现更加系统化且充分考虑现实设备功能，本文将该挑战称为路径标签空间浪费挑战，系统需要能够尽可能用少的比特位编码路径，同时生成最少的路由规则，以充分节省TCAM资源并降低数据包头开销。

% \textbf{C1: 路径标签冲突。} 给定一个路径集合$\Pi$，可以使用长度为$\lceil log_2 |\Pi| \rceil$的标签生成正确的数据平面配置容易，即为每个路径分配一个唯一的标签。然而，该数据平面配置不是最优的，它表示了最短路径标签长度的上限。当使用的比特位长度小于$\lceil log_2 |\Pi| \rceil$时，根据鸽笼原理~\cite{pigeonhole}，必然会有不同的路径被编码为相同的标签。如\cref{fig:dpg-label-conflict}所示的例子，网络中有6条路径需求，理论上需要3个比特位来编码所有路径，当使用2个比特位进行编码时，站在S1的视角需要两条路由规则，令其分别匹配0x和1x标签，由于H1-H5和H1-H6的路径同时经过S2，则S2中发往H5和H6的规则可以为10和11（或者11和10）。然而还有3条路径在S2上需要进行区分，如\cref{fig:dpg-label-conflict}红色路径所示，但是只剩下00和01标签可用，导致无法正确生成S2上的路由规则。本文将上述问题称为路径标签冲突挑战。

% \begin{figure}[tp]
%   \centering
%   \includegraphics[width=.8\linewidth]{figures/dpg/label-conflict.pdf}
%   \caption{标签冲突示例}
%   \label{fig:dpg-label-conflict}
% \end{figure}

% 令$\mathbb{R}=\{R_1,...,R_{|\mathbb{R}|}\}$为网络中所有的数据平面需求，对于任意两个需求$R_i(d_i, h_i, \pi_i), R_j(d_j, h_j, \pi_j) \in \mathbb{R}$，它们之间可能存在以下几种关系：
% \begin{enumerate}
% 	\item $H_i = H_j, \pi_i = \pi_j$;
% 	\item $H_i = H_j, \pi_i \neq \pi_j$;
% 	\item $H_i \neq H_j, \pi_i = \pi_j$;
% 	\item $H_i \neq H_j, \pi_i \neq \pi_j$。
% \end{enumerate}

% \textbf{数据平面配置冲突问题}。如图~\ref{fig:dp-conflict} 中所示的例子，网络中存在两个不同的需求，针对目的IP地址为10.0.0.2的数据包，$R_1$要求通过蓝色路径转发，而$R_2$要求通过绿色路径转发，如果直接根据包头和路径信息生成网络设备的转发规则，则在设备S2上出现两条互相冲突的规则。
% \begin{figure}[tp]
%   \centering
%   \includegraphics[width=.9\linewidth]{figures/dpg/dp-conflict.pdf}
%   \caption{数据平面冲突示例}
%   \label{fig:dp-conflict}
% \end{figure}

% \textbf{数据平面配置最优化问题。}

\section{基于定长编码的数据平面配置生成方法}
\label{sec:dpg-solution-fixed}
为了解决挑战C1（路径标签空间浪费），本文提出了基于定长编码的数据平面配置生成方法，该方法对路径通过的每个端口生成唯一一条路由规则，且所有规则具有相同的匹配域长度，并实现名为Fusion的系统。

\textbf{S1: 基于定长编码的数据平面配置生成方法。}对于网络$G(D,L)$，
% 令$\Omega_\mathbb{R}=\bigcup_{\rho \in \mathbb{R}}\rho.\pi$为所有数据平面需求路径所经过的端口集合，
需要对每个网络设备$d \in D$生成其数据平面配置$R_d$，为了实现占用设备资源尽可能小的数据平面配置，Fusion对每个端口只生成一条转发规则，令$r_d^{\psi} \in R_d$中action为转发到$\psi$的规则，需要计算$r_d^{\psi}$的match域。针对定长编码的数据平面配置生成，系统的任务是：1）为每个 $r_d^{\psi}$ 分配一个字符串标签 $l^\psi = \{0, 1, *\}^N$，其中标签长度为 $N$，$*$ 是通配符，可以匹配 0 或 1。2）为每个 $\pi \in \{\rho.\pi | \rho \in \mathbb{R}\}$ 分配一个二进制字符串标签 $L^\pi = \{0,1\}^N$。3）找到最小的 $N$，使得绑定路径 $\pi$ 的数据包可以在每个网络设备上正确转发。
% 令$l^\psi$表示发往端口$\psi$的规则对应的match域标签，则数据平面配置$T_d=\{(match:l^\psi, action: fwd(\pi))|\pi \in \Psi_d\}$。

接下来描述如何将这个过程建模为一个SAT问题。对于每条边 $a \in L$，标签 $l_a$ 可以写为 $\{x_a^1, x_a^2,...,x_a^N\}$，其中 $x_a^i \in \{0,1,*\}$ 是变 $a$ 的标签的第 $i$ 个值。由于每个 $x_a^i$ 有三个候选值，为了确定选择哪个值，需要使用两个布尔变量 $u_a^i, v_a^i$ 来表示 $x_a^i$ 的选择值。所以定义如下映射： $\overline{u}v = true$ 代表 0，$u\overline{v} = true$ 代表 1，$uv = true$ 代表 $*$。这样的映射方式的优势在已有工作如HSA~\cite{kazemian2012header}已经进行了研究。

\begin{theorem}
  \label{thm:dpg-conflict-bit}
  对于任意两个比特位$x_i=u_iv_i$和$x_j=u_jv_j$，它们对应的比特值不冲突当且仅当$\neg((u_i \oplus u_j) \wedge (v_i \oplus v_j)) = True$，表示为$x_i \sim x_j$。
\end{theorem}

\begin{proof}
  \cref{tab:dpg-conflict-bit}列出了\cref{thm:dpg-conflict-bit}对应的真值表，可以看到有且只有两种情况会发生冲突：1) $x_i=01, x_j=10$ 和 2）$x_i=10, x_j=01$。同时，有且只有这两种情况下对应编码方案给出的计算结果$\neg((u_i \oplus u_j) \wedge (v_i \oplus v_j))$均为0，其他情况均为1，可同时证明\cref{thm:dpg-conflict-bit}中条件的充分和必要性。
\end{proof}

\begin{table}
  \centering
	\caption{比特位编码的冲突判断真值表}
  \label{tab:dpg-conflict-bit}
  \begin{tabular}{|c|c|c|c|}
		\hline
		\diagbox{$u_iv_i (x_i)$}{$\neg((u_i \oplus u_j) \wedge (v_i \oplus v_j))$}{$u_jv_j (x_j)$} & 01 (0) & 10 (1) & 11 (*)
		\\\hline
		01 (0) &  1 &  0 (Conflict) &  1
		\\\hline
		10 (1) &  0 (Conflict) &  1 &  1
		\\\hline
		11 (*) &  1 &  1 & 1
		\\\hline
	\end{tabular}
\end{table}

\begin{theorem}
  \label{thm:dpg-conflict-label}
  对于任意两个长度为$N$的标签$l_i=\{x^i_1,...,x^i_N\}$和$l_j=\{x^j_1,...,x^j_N\}$，令$H_i$和$H_j$分别为$l_i$和$l_j$可匹配的包头空间，则$H_i \cap H_j \neq \emptyset$当且仅当$\forall k \in [1, N]: x^i_k \sim x^j_k$，表示为$l_i \sim l_j$。
\end{theorem}

\begin{proof}
  充分性：当$H_i \cap H_j \neq \emptyset$，说明$l_i$中具有取值为0或1的比特位在$l_j$中具有相同的值，反之亦然。根据\cref{thm:dpg-conflict-bit}，令$X={x^i_k|x^i_k \in \{0,1\}, x^i_k \in l_i}$，则$\forall x^i_k \in X: x^i_k \sim x^j_k$。而对于取值为*的比特位，根据\cref{tab:dpg-conflict-bit}，它与任何值都不冲突，所以$\forall k \in [1, N]: x^i_k \sim x^j_k$。

  必要性：当$\forall k \in [1, N]: x^i_k \sim x^j_k$，说明$l_i$中取值为0或1的比特位在$l_j$中具有相同的值，反之亦然。则$H_i \cap H_j \neq \emptyset$。
\end{proof}

基于上述定理，定义如下Overlap布尔函数，该函数输入两个标签$l_i$和$l_j$，如果输出为True表示$l_i$和$l_j$所对应的包头空间有交集，否则包头空间互斥。

\begin{equation}
  Overlap(l_i, l_j) = \begin{cases}
    1 & l_i \sim l_j \\
    0 & l_i \nsim l_j
  \end{cases}
\end{equation}

% 根据\cref{thm:dpg-conflict-bit}和\cref{thm:dpg-conflict-label}，当两个标签$l_i \sim l_j$，本文可以通过以下方式计算它们表示的包头空间的交集的标签表示，记为$l_k = l_i \wedge l_j$，其中$l_k = \{u^i_m v^i_m\}$

令$\Pi = \{\rho.\pi|\rho \in \mathbb{R}\}$为所有网络需求的路径集合，对于每个 $\pi \in \Pi$，$L_\pi$ 可以通过两个步骤构建：1）对所有的 $l_a \in \bigcup_{a \in \pi}l_a$，进行位逻辑与操作，得到结果 $\hat{L_\pi}$；2）从能够匹配 $\hat{L_\pi}$ 的二进制字符串中选择一个作为 $L_\pi$。

令$\Psi(\pi)=\{src(link)|link \in \pi\}$表示路径$\pi$经过的所有链接的起始端口，$l^\psi$表示action为发往端口$\psi$的规则标签，定义如下布尔函数：

\begin{equation}
  \label{equ:dpg-fwd}
  Fwd(\pi) = \bigwedge_{(\psi, \psi\prime) \in \Psi(\pi) \times \Psi(\pi)} Overlap(l^\psi, l^{\psi\prime})
\end{equation}

根据\cref{thm:dpg-conflict-label}，\cref{equ:dpg-fwd}为True表示路径$\pi$所经过的设备上发往对应端口的规则标签互不冲突，即存在一个$L^\pi$，它能够被发往对应端口的规则标签匹配。

基于上述描述，为了生成每条规则的标签，可以观察到必须满足以下两个约束条件。

\textbf{约束条件1}：对于每个 $\pi \in \Pi$，网络中存在满足$\pi$的路由规则，因此以下约束必须满足。
\begin{equation}
  C_1 = \bigwedge_{\pi \in \Pi} Fwd(\pi)
  \label{equ:c1}
\end{equation}

令$\Psi_{d}|_\psi = \Psi_d / \psi$为设备$d$的除了端口$\psi$以外的所有端口，定义如下Unique布尔函数：

\begin{equation}
  Unique(\pi) = \bigwedge_{\psi \in \Psi(\pi)}\bigwedge_{\psi\prime \in \Psi_{dev(\psi)}|_\psi}\neg Overlap(l^\psi, l^{\psi\prime})
\end{equation}

Unique函数输入一个路径$\pi$，当输出为True时，表示路径$\pi$经过的所有设备上对应规则的标签与该设备上其他规则标签所表示的包头空间交集为空，即在每个设备上只有一条规则能够处理路径$\pi$。

\textbf{约束条件2}：在每个设备上每条路径标签只能被唯一路由规则匹配，因此必须满足以下约束。

\begin{equation}
    C_2 = \bigwedge_{\pi \in \Pi} Unique(\pi)
    \label{equ:c2}
\end{equation}

现在的目标是找到满足\cref{equ:c1}和\cref{equ:c2}的赋值，并使标签长度 $N$ 最小，\cref{alg:dpg-fixed}给出了Fusion的算法概要，首先通过函数maxNumActions为网络设备中具有不同action数量最大值$m$，然后计算表示$m$数量的值需要的比特位数量，并将该值作为$N$的初始值，该值决定了$N$的下限（L1-2）。然后，算法根据$N$的取值生成相应的布尔变量集合（L6），并求解满足\cref{equ:c1}和\cref{equ:c2}的赋值（L7），如果找到可满足赋值，则返回变量取值结果，否则，将$N$的取值增加一并重新进行迭代（L5-8）。

\begin{algorithm}[]
  \caption{基于定长编码的数据平面配置生成算法}
  \label{alg:dpg-fixed}
  % \small
  \KwIn{$\Pi$: 网络路径集合; $G$: 网络拓扑}
  \KwOut{$vars$: 比特位编码}
  \SetKwProg{Fn}{Function}{:}{}
  $m \gets \FuncSty{maxNumActions}(\Pi, G)$\;
  $N \gets \lceil log_2 m \rceil$\;
  $sat \gets False$\;
  $vars \gets \{\}$\;
  \While{$sat \neq Ture$}{
    $vars \gets \FuncSty{GenVars}(G, N)$\;
    $sat \gets \FuncSty{Solve}(vars, C1, C2)$\;
    $N \gets N + 1$\;
  }
  \Return{$vars$}\;
\end{algorithm}

\begin{theorem}
  在基于定长编码的数据平面生成场景下，\cref{alg:dpg-fixed}实现了数据平面生成的正确性和最优性。
\end{theorem}

\begin{proof}
  首先，由于\cref{alg:dpg-fixed}的结果满足\cref{equ:c1}和\cref{equ:c2}，所以能够保证正确性。其次，由于每个设备上的规则数量等于实际所需的action数量，所以\cref{alg:dpg-fixed}生成的规则数量已经为下限值，同时，由于$N$的选取是从其下限值逐渐增加，最终得到的$N$一定是满足\cref{equ:c1}和\cref{equ:c2}的最小值。
\end{proof}

\section{基于前缀编码的数据平面配置生成方法}
\label{sec:dpg-solution-var}
基于定长编码的数据平面配置生成虽然能够满足正确性，同时在定长编码场景下实现了最优性，然而基于定长编码的方法具有以下局限性：1）没有考虑规则之间的优先级，即每个设备的路由规则匹配域均不重叠，这样的方法会导致更长的匹配域位宽，比如采用3个比特位的编码方法，一个设备上其中一条规则匹配包头空间0**，则其他的规则只能在1**所表示大小为4的包头空间内选择，如果对规则附加优先级（如最长前缀匹配LPM），则形如01*和00*的包头空间仍然可以被使用，可用包头空间增长为7个；2）任意匹配比特位可能发生在标签任意位置（如：0*0），这样的匹配规则在大部分网络设备上无法支持，比如传统路由设备只能支持LPM前缀匹配，导致数据平面配置生成方法使用场景受限。为了解决上述问题，本文进一步提出了基于前缀编码的数据平面配置生成方法。

\textbf{S2: 基于前缀编码的数据平面配置生成方法}。令$\Pi = \{\rho.\pi|\rho \in \mathbb{R}\}$为数据平面需求集合的所有路径集合，变量$x_\pi \in \mathbb{N}$为路径$\pi \in \Pi$对应的编码。令$\Omega_\mathbb{R}=\bigcup_{\pi \in \Pi}\pi$为所有数据平面需求路径所经过的所有端口集合，对于每个端口$port \in \Omega$，系统只生成一条数据平面规则$r_{port}$，最终形成数据平面配置$\mathbb{T}$。对于每条规则$r$，用两个变量$l_r,x_r \in \mathbb{N}$表示规则$r$的match域，其中$l_r$为前缀长度，$x_r$为match域的前缀值。例如，IPv4前缀10.0.0.0/8用上述变量表示为$l_r = 8, x_r = 10$。由于数据平面对于前缀匹配通常使用最长匹配（Longest prefix match, LPM）规则，所以$l_r$同时也是$r$的优先级。

给定一个$l_r$和$x_r$，可以计算其能够匹配的包头空间，令整数区间$H_r = [start_r, end_r)$为规则$r$的match域所匹配的包头空间，其中：
\begin{equation}
	\label{equ:range}
	\begin{aligned}
	start_r & = x_r \times 2^{\mathcal{L} - l_r}\\
	end_r & = start_r + 2^{\mathcal{L} - l_r}
	\end{aligned}
\end{equation}

式~\ref{equ:range} 中$\mathcal{L}$表示协议允许的最长包头长度，$start_r$的值为$x_r$左移$\mathcal{L} - l_r$位，$end_r$的值为$start_r$加上前缀能够匹配的包头区间大小$2^{\mathcal{L} - l_r}$，例如前缀10.0.0.0/8（$l_r = 8, x_r = 10$）对应的区间为$[167772160, 184549376)$。

令$H_r(h): \mathbb{N} \rightarrow \{0,1\}$表示包头是否能够匹配规则$r$的布尔函数：
\begin{equation}
\label{equ:match-rule}
  H_r(h) = \begin{cases}
    1 & start_r \le h < end_r \\
    0 & start_r > h \vee end_r \le h
  \end{cases}
\end{equation}

基于上述定义，本文将数据平面生成问题描述为如下的整数规划问题：
\begin{subequations}
\label{equ:problem}
\begin{align}
	\min\quad & \max_{r \in \cup_{R \in \mathcal{R}} R}l_r \label{equ:dpg-goal}\\
	\st\quad  H_{r_{\psi}}(x_\pi) & = 1 & \forall \psi \in \pi, \forall \pi \in \Pi \label{equ:dpg-match}\\
	  H_{r_{\psi'}}(x_\pi) & \Rightarrow l_{r_{\psi'}} < l_{r_{\psi}} & \forall \psi'\neq \psi \in \Psi_{dev(\psi)}, \forall \psi \in \pi, \forall \pi \in \Pi \label{equ:dpg-conflict-free}\\
		l_r & \le \mathcal{L}, l_r \in \mathbb{N}  & \forall r \in \cup_{R \in \mathcal{R}}R \label{equ:dpg-var}\\
		x_r & \le 2^{l_r} - 1, x_r \in \mathbb{N}  & \forall r \in \cup_{R \in \mathcal{R}}R \label{equ:dpg-var1}\\
		x_\pi & \le 2^{\mathcal{L}} - 1, x_\pi \in \mathbb{N} & \forall \pi \in \Pi \label{equ:dpg-var2}
\end{align}
\end{subequations}

式~\ref{equ:dpg-goal} 为优化目标函数，目标希望$l_r$尽可能小，从而能够节省更多的TCAM~\cite{vishnoi2014effective}存储空间，由于不同规则具有不同的前缀长度，本文将目标定义为所有规则的前缀长度之和最小。传统网络设备转发表往往具有固定的流表结构，因此$R_d$占用的空间取决于$\max_{r \in R_d}l_r$，而新兴的可编程网络设备如RMT~\cite{vishnoi2014effective,chole2017drmt}支持自定义表结构，通过对不同的前缀长度进行分组以及内存排序可以实现更少的资源占用，该部分优化超出了本文的研究范畴，本文默认网络设备能够进行上述优化工作。

为了生成有效的数据平面配置，需要满足以下约束条件：约束条件~\ref{equ:dpg-match} 表示对于任意一条数据平面需求路径$\pi \in \Pi$，都存在相应的规则能够匹配路径编码$x_\pi$。约束条件~\ref{equ:dpg-conflict-free} 表示编码后的路径是无冲突的，即对任一条路径$\pi \in \Pi$，对任一个路径$\pi$经过的设备$d \in D$，其数据平面配置$R_d$中按照$\pi$转发的规则具有最高优先级。约束条件~\ref{equ:dpg-var}，~\ref{equ:dpg-var1} 和~\ref{equ:dpg-var2} 分别定义了$l_r$，$x_r$和$x_\pi$的取值范围，其中$\mathbb{N}=\{0,1,...\}$为自然数集合。

令$Conflict_{max}(\Pi)$表示数据平面需求路径$\Pi$中在同一个设备上冲突的最大数量，有如下定理：
\begin{theorem}
	当$Conflict_{max}(\Pi) > 2$时，数据平面生成问题为NP完全（NP-Complete）问题。
\end{theorem}

\begin{proof}
	本文将一个已知的NP完全问题$N$-SAT问题~\cite{huang2004complexity,wu2009complexity}归约到数据平面生成问题。令需求集合$\{\rho_1,...,\rho_N\}$在设备$d$上发生冲突，对应的转发端口为$\{\psi_i,...,\psi_N\}$，且$N > 2$，令变量$t_i \triangleq H_{r_{\psi_i}}(x_{\pi_i})$，由\cref{equ:range}和\cref{equ:match-rule}可知每个变量$t_i$的取值只依赖于$x_{\pi_i}, x_{r_{\psi_i}}, l_{r_{\psi_i}}$，对任意两个$t_i,t_j \in \{t_1,...,t_N\}$，$t_i$和$t_j$没有相同的依赖变量，所以$\{t_1,...,t_N\}$为自由变量集合。所以约束条件~\ref{equ:dpg-match} 可表示为每个子句只有一个变量的布尔表达式，该约束对应于一个{1-SAT}问题。令$hit_r \triangleq H_r / \cup_{l_{r'}>l_r}H_{r'}$为规则$r$可实际匹配的包头空间，定义函数$hit_r(h): \mathbb{N} \rightarrow \{0,1\}$如\cref{equ:match-rule}形式，令$y_i \triangleq hit_r(x_{\pi_i})$，由于$hit_r$总可以通过对$\mathbb{H}$进行划分后生成，所以$y_i$为自由变量。令$Y = \{y_1,...,y_N\}$，$Y|_{i} = Y / \{y_i\}$，针对无冲突约束，需要满足$\bigvee_i^N y_i\wedge_{y_j \in Y|_i}\bar{y_j}$，该布尔表达式每个子句具有$N$个自由变量，所以为一个N-SAT问题，由于$N$-SAT问题在$N > 2$时为一个NP完全问题，所以数据平面生成问题为NP完全问题。
\end{proof}

基于前缀编码的数据平面配置生成算法与\cref{alg:dpg-fixed}类似，唯一的不同在于算法不再需要变量$N$，也不再需要迭代$N$的值，同时变量集合从布尔变量变为了整数变量。为了更好地体现基于前缀编码的数据平面配置生成求解过程，用\cref{fig:dpg-var-example}所示的例子进行描述。网络中一共有3条需求路径用不同颜色标记，以设备S2为例说明其规则生成过程。

\begin{figure}[]
  \centering
  \includegraphics[width=0.75\linewidth]{figures/dpg/var-example.pdf}
  \caption{基于前缀编码的数据平面生成示例}
  \label{fig:dpg-var-example}
\end{figure}

\cref{fig:dpg-add}将$x_r$和$l_r$的取值用一个树形结构表示，为了简化表达，图中假设最长标签长度$\mathcal{L} = 2$，其中每个圆形节点中的标记表示$(x_r,l_r)$，方形的叶子节点表示了路径的可选标签，比如当一个路径被匹配标签$(0,1)$的规则匹配时，使用该路径的数据包将用包头0或者1进行转发。对规则match域的选择本质上是将规则与树中的节点进行映射，为了实现最短标签编码，标签分配过程采用广度优先搜索。比如，考虑路径$\pi_1$，可用为其分配标签$(0,0)$，如\cref{fig:dpg-add-r1}所示，$\pi_1$可选的标签包括0，1，2和3；考虑路径$\pi_2$，根据广度优先搜索，可用为其分配标签$(0,1)$，则$\pi_2$可选的标签为$\{0,1\}$，$\pi_1$的可选标签变为$\{2,3\}$，如\cref{fig:dpg-add-r2}所示；考虑$\pi_3$，依然按照广度优先搜索，为其分配标签$(1,1)$，然而会导致此时$\pi_1$的可用标签变为空集，如\cref{fig:dpg-add-r3e}所示，所以$\pi_3$对应规则的匹配域不能选择$(1,1)$，所以需要进一步进行搜索，从而为$\pi_3$对应规则分配标签$(0,2)$，此时可得到S2上的每个规则的匹配域，以及对应规则的标签值。上述过程描述了其中一个设备的规则生成，对于不同设备的FIB生成依然需要一致，以满足数据平面配置的正确性，其过程与上述过程类似，不同点在于当发生标签冲突时，需要对路径所经过的所有路由规则同时进行标签重新分配。

\begin{figure}[ht]
  \centering%
  \subcaptionbox{添加路径$\pi_1$ \label{fig:dpg-add-r1}}{%    
    \includegraphics[width=0.44\textwidth]{dpg/add-r1}}\hspace{2em}%
  \subcaptionbox{添加路径$\pi_2$ \label{fig:dpg-add-r2}}{%    
    \includegraphics[width=0.44\textwidth]{dpg/add-r2.png}}\quad
	\vskip0.5cm
  \subcaptionbox{添加路径$\pi_3$，导致$r_{S2\rightarrow S3}$失效 \label{fig:dpg-add-r3e}}{%    
    \includegraphics[width=0.44\textwidth]{dpg/add-r3e}}\hspace{2em}
  \subcaptionbox{对于路径$\pi_3$搜索下一个可用节点 \label{fig:dpg-add-r3}}{%    
    \includegraphics[width=0.44\textwidth]{dpg/add-r3.png}}
  \caption{设备S2的规则生成过程}
  \label{fig:dpg-add}
\end{figure}


% \subsection{数据平面生成系统设计}
% 整体架构如图\ref{fig:fusion-arch}所示，网络中的元素分为两组，边缘和核心。不同流的路径被建模为一棵路径决策树，这是\cite{maple}中的一个"trace tree"，派生的路径被送入路径数据库，路径编码器（一个SAT求解器）负责为每条路径计算最优标签和交换机的规则。控制器从路径数据库生成转发表，作为每个交换机上的共同管道（在图\ref{fig:fusion-arch}中标为绿色），而路径决策管道仅部署在边缘交换机上。路径决策管道源于路径决策树（在图\ref{fig:fusion-arch}中标为蓝色），其中路径标签被派生并注入到数据包中（本文忽略路径标签的删除，因为这不是本文关注的重点）。
% \begin{figure}[tp]
%   \centering
%   \includegraphics[width=1\linewidth]{figures/dpg/ope-arch.pdf}
%   \caption{Overall architecture}
%   \label{fig:fusion-arch}
% \end{figure}

\section{实验设计和结果分析}
\label{sec:dpg-eval}
为了评估Fusion的效果，实验选择了不同的真实拓扑结构，实验主要回答以下问题：
\begin{enumerate}
  \item Fusion是否能够生成满足所有路径需求的数据平面配置？
  \item 相比已有工作，Fusion是否能够生成的更优的数据平面配置？
  % \item Fusion的定长和前缀编码方式
  % \item Fusion生成数据平面配置时间开销多大？
\end{enumerate}

\subsection{系统实现}
Fusion基于Z3~\cite{z3} SMT Solver实现~\footnote{https://github.com/guodong/fusion}，针对定长编码和前缀编码分别采用布尔变量和整数变量，并将系统分别命名为Fusion-fixed和Fusion-var。由于Fusion-fixed需要迭代选取标签长度取值，直到找到可满足的变量赋值，系统用$\lceil log_2(X) \rceil$作为标签长度$N$的初始值，其中$X$表示所有网络设备中，有效端口（路径所通过的端口）数量的最大值。

\subsection{Fusion生成数据平面配置效果评估}
\textbf{实验设计。}
实验从RocketFuel\cite{rocketfuel}和Topology zoo\cite{topologyzoo}中选择了不同规模的网络拓扑，如\cref{tab:dpg-eval-network}所示。实验计算所有节点之间的最短路径作为网络需求路径，并比较了以下数据平面配置生成方法：

\begin{enumerate}
  \item Baseline：对于一个有$M$个节点的网络，总共的路径数目为$M \times (M-1)$，用长度为整数$N \in \mathbb{Z}$的比特序列对所有路径进行编码，$N = \lceil log_2 (M \times (M-1))\rceil$。
  \item Path switching: 基于Path switching\cite{opo}方法计算每个规则的标签。
  \item Fusion-fixed: 基于定长编码的数据平面配置生成。
  \item Fusion-var: 基于前缀编码的数据平面配置生成。
\end{enumerate}

对于Baseline的结果可以直接通过路径数量得到，Path switching的结果来自其文献，结果列在\cref{tab:dpg-eval-network}的第5/6列中。Fusion使用Z3求解器\cite{z3}来求解编码约束问题，对于定长编码方式，Fusion通过逐渐增加比特宽度$N$，直到找到一个满足的赋值。得到数据平面配置后，将数据平面配置输入Flash对每个路径进行可达性验证，并计算成功可达的路径比率。

\begin{table}[ht]
	\centering
	\caption{数据平面配置生成实验结果}
  \small
	\begin{tabular}{|c|c|c|c|c|c|c|c|}
		\hline
		网络 & \#节点 & \#链路 & \#路径 & Baseline & PS\cite{opo} & \makecell{Fusion-fixed(验证通过比)/\\Fusion-var(验证通过比)}\\ 
		\hline
		4323:4323 & 51 & 323 & 2,550 & 26 & 16 & \makecell{8 (100\%) / 8(100\%)} \\\hline
		3549:3549 & 61 & 972 & 3,660 & 25 & 17 & \makecell{9 (100\%) / 8(100\%)} \\\hline
		Abilene & 11 & 28 & 110 & 9 & 7 &  \makecell{3 (100\%) / 3(100\%)} \\\hline
		ATMnet & 21 & 44 & 420 & 12 & 11 &  \makecell{4 (100\%) / 3(100\%)} \\\hline
		BBNPlanet & 27 & 56 & 702 & 14 & 10 &  \makecell{7 (100\%) / 5(100\%)} \\\hline
		BICS & 33 & 96 & 1,056 & 17 & 13 &  \makecell{8 (100\%) / 7(100\%)} \\\hline
		Chinanet & 42 & 132 & 1,772 & 9 & 7 &  \makecell{8 (100\%) / 6(100\%)} \\
		\hline
	\end{tabular}
	\label{tab:dpg-eval-network}
\end{table}

\textbf{实验结果。}
实验结果如\cref{fig:dpg-eval-size}所示。可以看到，与Baseline相比，Fusion-fixed编码长度减少了22\%-69\%，Fusion-var的编码长度减少了33\%-75\%。与Path switching\cite{opo}相比，Fusion-fixed编码长度最多减少63\%，Fusion-var编码长度最多可减少73\%。同时，所有的数据平面生成结果都能够实现100\%通过可达性验证，如\cref{tab:dpg-eval-network}最后一列所示，即Fusion-fixed和Fusion-var均可以生成正确的路由。由此可见，相比已有工作，Fusion可以生成正确且更优的数据平面配置。

\begin{figure}
  \centering
  \includegraphics[width=0.78\linewidth]{figures/dpg/eval-size.pdf}
  \caption{最长编码长度比较}
  \label{fig:dpg-eval-size}
\end{figure}

由于Fusion依赖Z3求解器来构建大量的变量和约束条件，而Z3采用DPLL~\cite{davis-putnam-1960}算法实现全面的求解过程，不同的输入规模可能引起显著的求解时间差异。在这方面，Fusion的定长编码和前缀编码存在明显的输入规模差异。为了比较它们在计算方面的差异，本研究进一步评估了Fusion的时间开销。

\textbf{实验设计。}
为了评估Fusion的时间开销，实验收集了Fusion-fixed和Fusion-var生成数据平面配置的执行时间。

\textbf{实验结果。}
实验结果如\cref{fig:dpg-eval-time}所示，其中，Fusion-fixed方法的执行时间在6s-16,309s（约4.5小时）之间，而Fusion-var方法的执行时间在2s-51s之间。Fusion-fixed的时间在所有拓扑下都要比Fusion-var长，主要原因在于1）Fusion-fixed求解约束涉及的变量要比Fusion-var多。2）Fusion-fixed每次将$N$增加一实现迭代计算，计算过程中会有产生大量的冗余计算，导致计算时间较长。

\begin{figure}
  \centering
  \includegraphics[width=0.78\linewidth]{figures/dpg/eval-time.pdf}
  \caption{编码时间比较}
  \label{fig:dpg-eval-time}
\end{figure}

\section{本章小结}
本章的核心研究问题是如何生成满足多样化的网络协同应用编程生成需求的数据平面配置。首先分析了网络协同应用编程中存在的“路由冲突”现象，基于这一现象引出如何生成正确且最优的数据平面配置问题，该问题具有路径标签浪费挑战。为了应对该挑战，提出了数据平面配置生成系统Fusion。Fusion实现了基于定长和前缀编码的方法。最后，通过实验验证，Fusion相较于现有方法能够将路由规则匹配域长度缩减75\%。